package dag

import (
	"errors"
	"fmt"
)

type TDagNode[T comparable] struct {
	Key   T   //键
	Deps  []T //依赖
	index int //用此可以描述最深层次，这里如果不用，那就需要用递归时用一个Hash来持有此次已走过路径的Key
}

type TGetDagNode[T comparable] interface {
	GetDagNode() *TDagNode[T]
}

type tOnAddNode func(node interface{})

func (n *TDagNode[T]) setIndex(value int) {
	n.index = value
}

func (n *TDagNode[T]) recursion(deps []T, mapData, mapNodes map[T]interface{}, prevIndex int, onAdd tOnAddNode) (state int, info string) {
	if n.index != 0 { //有环
		return 1, fmt.Sprintf("%v", n.Key)
	}
	currIndex := prevIndex + 1
	n.setIndex(currIndex) //用index来检查是否有环
	defer n.setIndex(0)
	for _, key := range deps {
		if data, ok := mapData[key]; ok { //没有此节点
			if _, ok1 := mapNodes[key]; !ok1 { //没有加过的
				mapNodes[key] = data
				node := data.(TGetDagNode[T]).GetDagNode() //这里不需要再检查了
				state, info = node.recursion(node.Deps, mapData, mapNodes, currIndex, onAdd)
				switch state {
				case 2, 3:
					return state, info
				case 1:
					return 1, fmt.Sprintf("%v-->%s", n.Key, info)
				}

			} else { //已经找过的
				continue
			}
		} else {
			return 3, fmt.Sprintf("没有此节点：%v", key)
		}
	}
	onAdd(n)
	return 0, "" //成功
}

func TopologySort[T comparable](list []interface{}) (nodes []interface{}, err error) {
	mapNodes := make(map[T]interface{}, len(list))
	mapData := make(map[T]interface{}, len(list))
	nodes = make([]interface{}, len(list))

	for _, v := range list {
		if iNode, ok := v.(TGetDagNode[T]); ok {
			node := iNode.GetDagNode()
			if node == nil {
				return nil, fmt.Errorf("GetDagNode返回节点数据为空，%v", iNode)
			}
			if _, ok1 := mapData[node.Key]; ok1 {
				return nil, fmt.Errorf("有重复KEY，%v", node.Key)
			}
			mapData[node.Key] = v
		} else {
			return nil, fmt.Errorf("节点没有对应的TDagKey接口：%v", v)
		}
	}
	index := 0
	onAddFunc := func(node interface{}) {
		nodes[index] = node
		index++
	}

	for _, v := range list {
		node := v.(TGetDagNode[T]).GetDagNode() //这里不需要再检查了
		if _, ok := mapNodes[node.Key]; ok {
			continue //已经加载过
		}
		state, info := node.recursion(node.Deps, mapData, mapNodes, 0, onAddFunc)
		switch state {
		case 1:
			return nodes, fmt.Errorf("有闭环错误，%s", info)
		case 2, 3:
			return nodes, errors.New(info)
		}
	}

	return nodes, nil
}

func NewDagNode[T comparable](key T, deps []T) *TDagNode[T] {
	return &TDagNode[T]{Key: key, Deps: deps}
}
